//
// Created by sjjmw on 1/21/2022.
//

#ifndef LEETCODE__343_H
#define LEETCODE__343_H
#include "base.h"
#include "stdlib.h"

class Solution
{
public:
    int integerBreak(int n)
    {
        vector<int> dp(57); //1-58
        dp[0] = 1;
        for (int i = 2; i <= n; i++)
        {
            //n 3:1  4:1,2 5:1,2 6:1,2,3
            int _max = 0;
            for (int j = 1; j <= i / 2; j++)
            {
                int a = max(j, dp[j - 1]) * max(i-j,dp[i - j - 1]) ;
                if (a > _max)
                {
                    _max = a;
                }
            }
            dp[i - 1] = _max;
        }
        return dp[n - 1];
    }
};

int main()
{
    Solution sol;
    sol.integerBreak(10);
    return 0;
}
#endif //LEETCODE__343_H
